package caculate.strSearch;

import java.util.Arrays;

/**
 * @program: rocsun
 * @description:
 * @author: yx.guo
 * @create: 2025-02-28 12:40
 **/
class BM extends StrMethod {

    public BM(String str, String pattern) {
        super(str, pattern);
    }

    /**
     * BM算法
     *  坏字符规则
     *      坏字符表
     *          int[] badTable = new int[256];
     *  好后缀规则
     *      好后缀表
     *          boolean prefix[]
     *          int suffix[]
     * @return
     */
    @Override
    protected int searchStr() {
        int[] badTable = this.buildBadTable();
        int[] suffix = new int[pLen];
        boolean[] prefix = new boolean[pLen];
        buildGoodSuffix(suffix, prefix);
        int i = 0;
        while (i < sLen) {
            int j;
            for (j = pLen - 1; j >= 0; j--) {
                if (str.charAt(i + j)  != pattern.charAt(j)) {
                    break;
                }
            }

            if (j < 0) {
                return i;
            }

            int badCharOffset = j - badTable[str.charAt(i + j)]; // 坏字符移动位数
            int goodSufOffset = calGoodSufOffset(i, j, suffix, prefix);// 好后缀移动位数
            i += Math.max(badCharOffset, goodSufOffset);
        }

        return -1;
    }

    /**
     *
     * @param i 窗口起始位置索引
     * @param j 坏字符位置索引
     * @param suffix 好后缀表
     * @param prefix 是否存在指定长度的前缀等于后缀表
     * @return
     */
    private int calGoodSufOffset(int i, int j, int[] suffix, boolean[] prefix) {
        // 最小移动单位
        int k = pLen - 1 - j;
        if (k == 0) {
            return 1;
        }

        // 次一级移动单位 (存在指定长度的好后缀在字符中间)
        int sufIndex = suffix[str.charAt(i + j)];
        if (sufIndex != -1) {
            return j - sufIndex + 1;
        }

        // 高一级的移动单位
        while (k > 0) {
            if (prefix[k--]) {
                return pLen - k;
            }
        }

        // 最该级移动策略
        return pLen;
    }

    /**
     * 构建好后缀表
     *   这里需要做几件事
     *      1. 找出后缀在前面出现的位置
     *      2. 如果在字符串口头出现，记录一下
     * @param suffix
     * @param prefix
     */
    private void buildGoodSuffix(int[] suffix, boolean[] prefix) {
        Arrays.fill(suffix, -1);
        Arrays.fill(prefix, false);
        int i = 1;
        while (i < pLen - 1) {
            int left = i;
            int right = pLen - 1;
            while (left >= 0) {
                if (pattern.charAt(left) != pattern.charAt(right)) {
                    break;
                }

                left--;
                right--;
                suffix[i - left] = left;
            }

            if (left + 1 ==  0) {
                prefix[i + 1] = true;
            }
            i++;
        }

    }

    /**
     * 坏字符表
     * @return
     */
    private int[] buildBadTable() {
        int[] badTable = new int[256];
        Arrays.fill(badTable, -1);

        for (int i = 0; i < pLen; i++) {
            badTable[pattern.charAt(i)] = i;
        }

        return badTable;
    }

}
